package com.aqie.easy.string;

import java.util.*;

/**
 *
 * 748最短完整词
 * 字符串包含 ： contains、matches、regionMatches、indexOf
 */
public class ShortestCompletingWord {
    public static String shortestCompletingWord(String licensePlate, String[] words) {
        // 找出字符串中 要查找的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < licensePlate.length(); i++){
            if (Character.isLetter(licensePlate.charAt(i))){
                stringBuilder.append(licensePlate.charAt(i));
            }
        }
        Queue<String> queue = new LinkedList<>();
        String target = stringBuilder.toString().toLowerCase();
        for (String word : words) {
            if (compareStrings(word, target)) {
                if (queue.isEmpty()) {
                    queue.add(word);
                } else if (queue.peek().length() > word.length()) {
                    queue.poll();
                    queue.add(word);
                }
            }
        }
        if (queue.isEmpty()) return "";
        return queue.peek();
    }

    /**
     * A 中 包含 B 中所有字符串返回 true
     * @param A
     * @param B
     * @return
     */
    public static boolean compareStrings(String A, String B) {
        // write your code here
        int[] index = new int[26];
        for (int i = 0; i < A.length(); i++) {
            index[A.charAt(i) - 'a']++;
        }
        for (int i = 0; i < B.length(); i++) {
            index[B.charAt(i) - 'a']--;
            if(index[B.charAt(i) - 'a'] < 0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String licensePlate = "1s3 456";
        String []words = {"looks", "pest", "stew", "show"};

        String licensePlate2 = "1s3 PSt";
        String[] words2 = {"step", "steps", "stripe", "stepple"};

        // 找出字符串中 要查找的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < licensePlate2.length(); i++){
            if (Character.isLetter(licensePlate2.charAt(i))){
                stringBuilder.append(licensePlate2.charAt(i));
            }
        }
        Queue<String> queue = new LinkedList<>();
        String target = stringBuilder.toString().toLowerCase();
        for (int i = 0; i < words2.length; i++){
            if (compareStrings(words2[i], target)) queue.add(words2[i]);
        }
        System.out.println(queue.peek());


        String A = "hellii";
        String B = "helli";
        System.out.println(compareStrings(A, B));

        System.out.println(shortestCompletingWord(licensePlate, words));
    }
}
